const color = {
    red: true,
    black: false
}

class Node {
    constructor(key = null, value = null) {
        this.key = key
        this.value = value
        this.left = null
        this.right = null
        this.color = color.red
    }
}

export class RBTree {
    constructor() {
        this.root = null
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    isRed(node) {
        if (node === null) {
            return color.black
        }
        return node.color
    }

    leftRotate(node) {
        const x = node.right

        node.right = x.left
        x.left = node

        x.color = node.color
        node.color = color.red

        return x
    }

    rightRotate(node) {
        const x = node.left

        node.left = x.right
        x.right = node

        x.color = node.color
        node.color = color.red

        return x
    }

    flipColors(node) { // 颜色翻转
        node.color = color.red
        node.left.color = color.black
        node.right.color = color.black
    }

    add(key, value) {
        this.root = this._add(this.root, key, value)
        this.root.color = color.black
    }

    _add(node, key, value) {
        if (node === null) {
            this.size++
            return new Node(key, value)
        }

        if (node.key > key) {
            node.left = this._add(node.left, key, value)

        } else if (node.key < key) {
            node.right = this._add(node.right, key, value)

        } else {
            node.value = value

        }

        if (this.isRed(node.right) && !this.isRed(node.left)) {
            node = this.leftRotate(node)
        }

        if (this.isRed(node.left) && this.isRed(node.left.left)) {
            node = this.rightRotate(node)
        }

        if (this.isRed(node.left) && this.isRed(node.right)) {
            this.flipColors(node)
        }

        return node
    }

    getNode(node, key) {
        if (node === null) {
            return null
        }

        if (key === node.key) {
            return node

        } else if (key < node.key) {
            return this.getNode(node.left, key)

        } else {
            return this.getNode(node.right, key)

        }
    }

    contains(key) {
        return this.getNode(this.root, key) !== null
    }

    get(key) {
        const node = this.getNode(this.root, key)
        return node === null ? null : node.value
    }

    set(key, value) {
        const node = this.getNode(this.root, key)
        if (node === null) {
            throw new Error(`${key} doesn't exist!`)
        }
        node.value = value
    }

}